/**
 * 剑指 Offer 31. 栈的压入、弹出序列（与 946 同）
 * https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 */
public class Solutions_Offer_31 {
    public static void main(String[] args) {
        int[] pushed = {1, 2, 3, 4, 5};
//        int[] popped = {4, 5, 3, 2, 1};  // output: true
        int[] popped = {4, 3, 5, 1, 2};  // output: false

        boolean result = validateStackSequences(pushed, popped);
        System.out.println(result);
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        int len = pushed.length;
        // 模拟栈，入栈和弹栈操作
        int[] stack = new int[len];
        int push_index = 0, pop_index = 0;

        for (int i = 0; i < len; i++) {
            // 元素入栈
            stack[push_index ++] = pushed[i];
            // 当前栈顶元素与 popped[pop_index] 相同时，元素出栈
            while (push_index > 0 && stack[push_index - 1] == popped[pop_index]) {
                pop_index ++;
                push_index --;
            }
        }
        // 最终栈中为“空”即说明可以将全部元素出栈，popped 是合法的出栈序列
        return push_index == 0;
    }
}
